/**
 * 常见的数据结构：队列，栈，链表，树，用来存储数据的
 *  队列：先进先出，push shift 事件环
 *  栈：后进先出，unshift,pop,方法的调用栈，路由切换，浏览器的历史记录（两个栈）
 *  数组的shift是比较浪费性能的，每次弹出一个后续内容往前移位
 *
 * 链表：线性表的链式存储结构
 * 链表查找 删除的性能平均复杂度O(n)，起码要遍历一遍
 * 可以用链表模拟队列和栈，头尾操作比较方便，优化数组shift的功能
 *
 * */

class Node {
  constructor(element, next) {
    this.element = element;
    this.next = next;
  }
}
class LinkedList {
  constructor() {
    this.head = null; // 头，默认是空
    this.size = 0; // 链表长度
  }
  /**
   * 增加节点，不是覆盖
   * @param {索引} index
   * @param {节点} element
   */
  add(index, element) {
    // 只有一个参数，就是向末尾添加
    if (arguments.length === 1) {
      element = index;
      index = this.size;
    }

    if (index < 0 || index > this.size) {
      throw new Error('链表索引异常');
    }

    if (index === 0) {
      // 第一项
      let head = this.head; // 老的头
      this.head = new Node(element, head);
    } else {
      // 获取前一个节点
      let prevNode = this.getNode(index - 1); // 前面节点肯定有，没有就走if
      prevNode.next = new Node(element, prevNode.next);
    }

    // console.log(index, element);
    // 累加链表长度
    this.size++;
  }
  // 删除节点
  remove(index) {
    let oldNode;
    if (index === 0) {
      // 删除第一个,
      oldNode = this.head;
      this.head = oldNode && oldNode.next;
    } else {
      // 获取当前的前一个节点
      let prevNode = this.getNode(index - 1);
      oldNode = prevNode.next; // 前一个的下一个就是要删除
      prevNode.next = prevNode.next.next; // 让前一个下一个指向之前的下一个
    }
    this.size--;
    return oldNode && oldNode.element; // 返回当前的节点
  }
  // 获取节点
  getNode(index) {
    let current = this.head; // 重头找
    for (let i = 0; i < index; i++) {
      current = current.next;
    }
    return current;
  }
  // 列表的个数
  length() {
    return this.size;
  }

  // 翻转链表，两两翻转 深度优先 这种递归的方式，就是找到最后两个，然后从后往前反转
  // 可以理解为 套了3层函数 最里边的先执行 从里往外执行, 单叉树
  // 改变指针指向，没有交换位置
  reverseLinkedList() {
    // 先递归最里面的，再出来
    function reverse(head) {
      // 如果链表为空，或者没有下一个了，就不用转了
      if (head == null || head.next == null) return head;
      // 两个节点翻转
      let newHead = reverse(head.next); // 将原来的一下个变成头结点
      head.next.next = head; // 让下一个节点的下一个指向原来的头
      head.next = null; // 让老头指向null
      return newHead;
    }
    this.head = reverse(this.head);
    return this.head;
  }
  /**
   *  循环
   */
  reverseLinkedList2() {
    // 保存旧的头部
    let oldHead = this.head;
    if (oldHead == null || oldHead.next == null) return oldHead;

    let newHead = null; // 新的链表头部默认指向null

    while (oldHead !== null) {
      let temp = oldHead.next; // 存储当前的下一个,100
      oldHead.next = newHead; // 让老的头指向新的头
      newHead = oldHead; // 让新的头指向老的头
      oldHead = temp; // 让老的头向后移动
    }

    this.head = newHead;
    return this.head;
  }
}

let ll = new LinkedList();
// 往索引0处添加
ll.add(0, 100);
ll.add(0, 200);
// 不加索引，就是向末尾添加
ll.add(300); // 顺序 200 100 300
// ll.remove(0);
// console.log(ll.head);

// let reverseList = ll.reverseLinkedList();
// console.log(reverseList);
let reverseList2 = ll.reverseLinkedList2();
console.log(reverseList2);
